%\documentclass[zihao=-4]{ctexbook} % 字号
\documentclass[UTF8, zihao=-4]{ctexart} % 字号
%强制字体设置 (use with xelatex)
%\setCJKmainfont{NSimSun}
%\setCJKmainfont{WenQuanYi Micro Hei}
%\setCJKmainfont{WenQuanYi Zen Hei}
%\setCJKmainfont{KaiTi_GB2312}

%if use with engine pdflatex: set the following
%\documentclass[UTF8, zihao=-4, zhmap=zhmCJK, fontset=none]{ctexart} % 字号
%\usepackage{zhmCJK}
%\setCJKmainfont{simsun.ttc}
%\setCJKsansfont{simkai.ttf}
%\setCJKmonofont{simfang.ttf}

\usepackage[colorlinks=false, backref=true]{hyperref} % PDF 目录
\usepackage{graphicx} % 包含图形文件
\usepackage{xcolor} % 颜色
\usepackage{geometry} % 版面边距
\usepackage{fancyhdr} % 定制页眉页脚

% 数学符号
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathrsfs}

\usepackage{multirow} % 多行表格
\usepackage{multicol} % 多列表格
\usepackage{animate} % PDF 动画
\usepackage{tabu} % 高级表格
\usepackage{listings} % 插入代码

\usepackage{extarrows} % 高级箭头
\usepackage[all]{xy} % 交换图表

% 参考文献库
\usepackage[backend=biber, style = caspervector, utf8, sorting = ecnty]{biblatex}
% sorting: none 引用顺序 ecnty 英文在先 centy 中文在先
% 引用 \cite(supercite, parencite) [prenote][postnote]{key}
% prenote: 标号前置文字; postnote: 标号后置文字; key: 引用标签
% cite 无格式化标号 parencite [标号] supercite 上标标号
% \fullcite 打印完整参考文献条目
% 使用 biber -l zh__pinyin (zh__stroke) texfile 编译参考文献
% 打印文献列表: 
%     \printbibliography[title = {参考文献}, heading = bibnumbered]
%      title: 文献列表标题; 
%      heading: 
%           bibnumbered : 文献列表参与章节编号, 并被列入目录;  
%           bibintoc : 文献列表被列入目录中, 但不参与章节编号.

% 指定页面边距
\geometry{%
  a4paper,%
  top=2.5cm,%
  bottom=2.5cm,%
  left=3.2cm,%
  right=3.2cm%
}

% 指定章节标题
\ctexset {
      part = {
            name = {（,）}, % number 前的名字, number 后的名字
            % number 的样式 \chinese{part|section} 表示中文编号, \arabic 为数字
            % \Roman{...} 罗马数字, \roman{...} 小写罗马数字, \alph \Alph 小写, 大写字母
            number = {\chinese{part}}, 
            format = {\large\bfseries\color{blue}} % 文字样式: 大小+颜色
            % aftername = {\hspace{0.3cm}}
            % aftername 为章节编号与标题文本之间的内容
      },
      section = {
            format = {\large\rm\color{blue}}
      }
}

% 预定义常用数学符号
\newcommand{\real}{\mathbb{R}} % 实数
\newcommand{\comp}{\mathbb{C}} % 复数
\newcommand{\inte}{\mathbb{Z}} % 整数
\newcommand{\nat}{\mathbb{N}} % 自然数
\newcommand{\prob}{\mathbb{P}}
\newcommand{\expe}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\co}{\mathcal{O}}
\newcommand{\id}{\text{Id}}
\newcommand{\im}{\text{Im}}
\newcommand{\End}{\text{End}}
\newcommand{\proof}{{\itshape 证明.}}
\newcommand{\lcode}{\lstinline} % 段内插入代码

%mathbb 双透明体 (用于固定空间)
%mathbf 粗体
%mathcal 圆体 (用于算子)
%mathfrak 正体 (用于范畴)
%mathscr 花体 (用于集合系)

%\newtheorem{label}[共享编号来源(环境, 不是计数器)]{标题文本}[父计数器]
\newtheorem{theo}{定理}
\newtheorem{prop}{命题}
\newtheorem{problem}{算例}
\newtheorem{corollary}{推论}
\newtheorem{algorithm}{算法}

% 增加文献库
\addbibresource{teng.bib}
%\addbibresource{tda.bib}

% 设置每个 part 重置 section 编号
\makeatletter
\@addtoreset{section}{part}
\makeatother
%计数器命名: part, chapter(book), section, subsection, subsubsection, page,
%所有 newtheorem 定义的环境, equation, figure, table, footnote, 
%enum~(i, ii, iii, iv) 序列表环境中的编号.
%\setcounter{计数器}{值} 设置计数器的值.

% 设置页眉页脚

%\pagestyle{empty} %无页眉页脚
%\pagestyle{fancy} %定制页眉页脚

%\fancyhf{} %clear all head and foot
%\fancyhf[HF EO LCR,... (位置)]{内容} 数值页眉页脚
%H: Header F: Footer E: Even O: Odd L: left C: center R: right
%\renewcommand{\headrulewidth}{0.5pt} % width of head line
%\renewcommand{\footrulewidth}{0pt} % clear foot line
%\thetitle 标题 \thepage 页码 \thechapter \thesection 章节标题

% 修改名字为 plain 的页面样式 {} 内包含上一段中的命令
% 标题, 目录和章标题页面默认均为 plain 样式, 因此改变这些页面的样式只能使用本命令.
%\fancypagestyle{plain}{
%}

%\thispagestyle{plain} 改变当前页面的样式为 plain

%重定义图表的引词
%\renewcommand\figurename{\rm 图}
%\renewcommand\tablename{\rm 表}

% 配置代码插入的风格
\lstset {
    language            =   go,                  % 代码语言
    basicstyle          =   \ttfamily,          % 基本代码风格
    keywordstyle        =   \color{blue}, % 关键字风格
    commentstyle        =   \ttfamily,  % 注释的风格，斜体
    stringstyle         =   \bfseries\ttfamily,  % 字符串风格
    flexiblecolumns,                % 别问为什么，加上这个
    %numbers             =   left,   % 行号的位置在左边
    %showspaces          =   false,  % 是否显示空格，显示了有点乱，所以不现实了
    %numberstyle         =   \zihao{-5}\ttfamily,    % 行号的样式，小五号，tt等宽字体
    showstringspaces    =   false,  % 是否显示 string 内部的空格
    captionpos          =   t,      % 这段代码的名字所呈现的位置，t指的是top上面
    frame               =   lrtb,   % 显示边框
    breaklines          =   true,   % 自动换行
    columns             =   fixed,   
    basewidth           =   0.5em   % 字宽
}


\title{任意维整系数背包问题求解器 - 使用说明}
\date{最后更新日期: \today}
\author{滕飞}

\begin{document}

\maketitle

\section{问题简介}
\label{s1.1}
本求解器用于求解如下 $d$ 维整系数的背包问题, 详情请参考 \parencite{Yun90} \S 9.3.
\begin{equation}
      \label{e1}
      \begin{aligned}[]
            \max f &= \sum_{i=1}^n c_i (x_i) \\
            \text{s.t.} A x &\le b \\
            x & \ge 0, x \in \inte^n \\
            A & \in \inte^{d \times n} \\
            b & \in \inte^{d}
      \end{aligned}
\end{equation}
使用前请包含 
\begin{lstlisting}
import "gitee.com/tfcolin/knapsack" 
\end{lstlisting}

\section{算法简介}
本算法为动态规划方法, 具体采用递推公式
\begin{equation}
      \label{e2}
      \begin{aligned}[]
            f_k (s) & = \max \left\{ \right. & c_k(x_k) + f_{k-1} (s - A_k x_k) &  \\
              && : 0 \le x_k \le \min \left( s_l / a_{lk} : l = 1, \ldots, d \right) & \left. \right\} \\
             f_0(s) &= 0 &&
      \end{aligned}
\end{equation}
其中, $f_k(s)$ 表示在剩余背包容量为 $s \in \inte^{d}$ 的前提下, 装入第 $1$ 至 $k$ 种物品的最大价值.
$A_k$ 表示矩阵 $A$ 的第 $k$ 列. $a_{lk}$ 表示矩阵 $A$ 的第 $l$ 行 $k$ 列的元素. 上述取 $\max$ 时的
$x_k$ 即为第 $k$ 种物品的最优装入量.

\section{使用方法}
用户需首先调用
\begin{lstlisting}
func InitKnapsackData (dim int, num_item int) * KnapsackData
\end{lstlisting}
构造 \lcode{KnapsackData} 数据结构. \lcode{dim} 为问题维数 $d$, \lcode{num_item} 为
物品种类数 $n$. 接着, 用户需通过
\begin{lstlisting}
func (kd * KnapsackData) SetUtil (ii int, util_func UtilFunction)
\end{lstlisting}
设置物品的价值函数$c_i(x)$. 其中 \lcode{UtilFunction} 为函数类型, 定义为
\begin{lstlisting}
type UtilFunction func (x int) float64
\end{lstlisting}
可以使用预定义好的零函数 (\lcode{ZeroUtilFunc}) 或线性函数.
\begin{lstlisting}
func MakeScalarUtilFunction (c float64) UtilFunction
\end{lstlisting}
然后, 用户需调用如下函数设置限制条件 $Ax \le b$.
\begin{lstlisting}
func (kd * KnapsackData) SetLimit (limit_coef [][]int, limit []int)
\end{lstlisting}
其中, \lcode{limit_coef} 为矩阵 $A$, $a_{ij}$ 保存于 \lcode{limit_coef[i][j]}.
\lcode{limit} 为右端项 $b$. 

在完成相关参数的设置后, 用户可调用 
\begin{lstlisting}
func (kd * KnapsackData) Solve ()
\end{lstlisting}
来完成背包问题的求解. 最后, 可通过函数
\begin{lstlisting}
func (kd * KnapsackData) GetFinalValue () float64
func (kd * KnapsackData) GetFinalSelect (ii int) int 
\end{lstlisting}
获得计算结果. 其中, \lcode{GetFinalValue} 用于获取最优价值.
\lcode{GetFinalSelect} 用于获取第 \lcode{ii} 种物品的装载量,
即待定变量 $x$.

\printbibliography

\end{document}
